package com.demo.java.OD651_700.OD658;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【西天取经(A卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/147040738
 */
public class OdMain {
    public static int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 定义四个方向（上、下、左、右）
    public static int res = Integer.MAX_VALUE, sum = 0; // res用于存储最短路径，sum用于当前路径的步数
    public static boolean[][] visited; // visited用于记录每个点是否已访问
    public static int count = 0; // 记录爆发能力的使用次数

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(); // 行数
        int n = sc.nextInt(); // 列数
        int k = sc.nextInt(); // 高度差限制
        visited = new boolean[m][n]; // 初始化访问标记
        int[][] matrix = new int[m][n]; // 存储地图数据

        // 读取矩阵数据
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        // 从起点(0, 0)开始进行DFS搜索
        dfs(matrix, 0, 0, k);
        // 如果找到了合法路径，输出最短路径，否则输出-1
        System.out.println(res == Integer.MAX_VALUE ? -1 : res);
    }

    // 深度优先搜索
    public static void dfs(int[][] matrix, int x, int y, int k) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 如果到达终点(右下角)
        if (x == m - 1 && y == n - 1) {
            res = Math.min(res, sum); // 更新最短路径
            return;
        }

        // 如果当前点已经访问过，直接返回
        if (visited[x][y]) return;

        // 标记当前点已访问
        visited[x][y] = true;

        // 遍历四个方向的邻接点
        for (int[] d : directions) {
            int x1 = x + d[0];
            int y1 = y + d[1];

            // 如果邻接点越界，则跳过
            if (x1 < 0 || x1 >= m || y1 < 0 || y1 >= n) {
                continue;
            }

            // 如果邻接点的高度差小于等于k，可以直接走
            if (Math.abs(matrix[x1][y1] - matrix[x][y]) <= k) {
                sum++; // 增加路径长度
                dfs(matrix, x1, y1, k); // 递归搜索
                sum--; // 回溯，撤销路径长度
            } else {
                // 如果高度差大于k，且爆发能力使用次数小于2，可以使用爆发能力
                if (count > 2) continue;
                count++; // 使用一次爆发能力
                sum++; // 增加路径长度
                dfs(matrix, x1, y1, k); // 递归搜索
                count--; // 回溯，撤销爆发能力使用
                sum--; // 回溯，撤销路径长度
            }
        }

        // 标记当前点未访问，回溯
        visited[x][y] = false;
    }
}